package leetcode.backtrace;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class LeetCode417_PacificAtlantic {
	public List<List<Integer>> pacificAtlantic(int[][] matrix) {

		Deque<Integer> m;
		Deque<Integer> n;
		
		int[][] visited;
		boolean f1, f2, f3, f4;
		
		List<List<Integer>> r = new ArrayList<List<Integer>>();
		
		for(int i = 0; i < matrix.length; i++) {
			for(int j = 0; j < matrix[0].length; j++) {
				f1 = false;f2 = false;f3 = false;f4 = false;
				visited = new int[matrix.length][matrix[0].length];
				m = new LinkedList<>();
				n = new LinkedList<>();

				int x = i;
				int y = j;
				visited[i][j] = 1;
				if(y == 0) f1 = true;
				if(x == 0) f2 = true;
				if(y == matrix[0].length - 1) f3 = true;
				if(x == matrix.length - 1) f4 = true;
				
				if((f1 || f2) && (f3 || f4)) {
					List<Integer> t = new ArrayList<>();
					t.add(i);
					t.add(j);
					r.add(t);
					
					continue;
				}
				
				addToQueue(m, n, matrix, i, j);
				
				int tx = x;
				int ty = y;
				while(!m.isEmpty()) {
					int p = m.pop();
					int q = n.pop();
					if(visited[p][q] == 1 ) continue;
					//if(matrix[p][q] <= matrix[tx][ty]) {// 如果在这里处理，扩散条件中的大小关系会乱
						addToQueue(m, n, matrix, p, q);
					//}else continue;
					
					tx = p;
					ty = q;
					
					visited[p][q] = 1;
					
					if(q == 0) f1 = true;
					if(p == 0) f2 = true;
					if(q == matrix[0].length - 1) f3 = true;
					if(p == matrix.length - 1) f4 = true;
					
					if((f1 || f2) && (f3 || f4)) {
						List<Integer> t = new ArrayList<>();
						t.add(i);
						t.add(j);
						r.add(t);
						
						break;
					}
				}
				
				
			}
		}
		
		
		return r;
    }
	
	public void addToQueue(Deque<Integer> m, Deque<Integer> n, int[][] matrix,
			int i, int j) {
		if(0 <= i - 1 && matrix[i - 1][j] <= matrix[i][j]) {
			m.add(i - 1);
			n.add(j);
		}
		
		if(matrix.length > i + 1 && matrix[i + 1][j] <= matrix[i][j]) {
			m.add(i + 1);
			n.add(j);
		}
		
		if(0 <= j - 1 && matrix[i][j - 1] <= matrix[i][j]) {
			m.add(i);
			n.add(j - 1);
		}
		
		if(matrix[0].length > j + 1 && matrix[i][j + 1] <= matrix[i][j]) {
			m.add(i);
			n.add(j + 1);
		}
	}
	
	public static void main(String[] args) {
		int[][] data = 
			{{1,2,2,3,5,},
            {3,2,3,4,4,},
            {2,4,5,3,1,},
            {6,7,1,4,5,},
            {5,1,1,2,4,}};
		
		int[][] data2 = 
			{{1,}};
		
		List<List<Integer>> r = new LeetCode417_PacificAtlantic().pacificAtlantic(data2);
		r.forEach(e -> System.out.println(e.get(0) + "--" + e.get(1)));
	}
}
